/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package gov.nasa.jpf.search.heuristic;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 *
 * @author Frank
 */
public class ARTGenerator {

    private static final int MAX_VALUE = Integer.MAX_VALUE - 1;
    private Set<Integer> point;
    private List<Domain> candidate;
    private int range;
    private int radius;
    private int subsection;
    private Random random;

    public ARTGenerator(Random random) {
        this(MAX_VALUE, random);
    }

    public ARTGenerator(int range, Random random) {
        this.random = random;
        this.range = range;
        subsection = 2;
        radius = range / subsection;
        point = new HashSet<Integer>();
        candidate = new ArrayList<Domain>();
        candidate.add(new Domain(0, range));
    }

    public int getARTVal() {
        if (point.size() + 1 == MAX_VALUE) {
            return -1;
        }
        if (candidate.isEmpty()) {
            reAllocate();
        }
        int randomIndex = random.nextInt(candidate.size());
        int rangeFrom = candidate.get(randomIndex).getFrom();
        int rangeTo = candidate.get(randomIndex).getTo();
        int randomVal = rangeFrom + random.nextInt(rangeTo - rangeFrom);
        subtract(randomVal);
        point.add(randomVal);
        return randomVal;
    }

    private void reAllocate() {
        subsection++;
        radius = range / subsection;
        candidate.clear();
        candidate.add(new Domain(0, range));
        for (int i : point) {
            subtract(i);
        }
        if (candidate.isEmpty()) {
            reAllocate();
        }
    }

    private void subtract(int val) {
        long rangeFrom = val - radius;
        long rangeTo = val + radius;
        boolean fromChanged = false;
        boolean toChanged = false;
        int index = findPos(val);
        if (rangeFrom < 0 || rangeFrom > val) {
            rangeFrom = 0;
            fromChanged = true;
        }
        if (rangeTo > MAX_VALUE || rangeTo < val) {
            rangeTo = MAX_VALUE;
            toChanged = true;
        }
        if (rangeFrom < candidate.get(index).getFrom()) {
            rangeFrom = candidate.get(index).getFrom();
            fromChanged = true;
        }
        if (rangeTo > candidate.get(index).getTo()) {
            rangeTo = candidate.get(index).getTo();
            toChanged = true;
        }

        Domain preDomain = candidate.remove(index);
        if (fromChanged && !toChanged) {
            if ((int) rangeTo != preDomain.getTo()) {
                candidate.add(index, new Domain((int) rangeTo, preDomain.getTo()));
            }
        } else if (!fromChanged && toChanged) {
            if (preDomain.getFrom() != (int) rangeFrom) {
                candidate.add(index, new Domain(preDomain.getFrom(), (int) rangeFrom));
            }

        } else if (!fromChanged && !toChanged) {
            if (preDomain.getFrom() != (int) rangeFrom) {
                candidate.add(index, new Domain(preDomain.getFrom(), (int) rangeFrom));
            }
            if ((int) rangeTo != preDomain.getTo()) {
                candidate.add(index, new Domain((int) rangeTo, preDomain.getTo()));
            }
        }

    }

    private int findPos(int val) {
        int index = 0;
        int size = candidate.size();
        while (index < size) {
            if (candidate.get(index).contains(val)) {
                return index;
            }
            index++;
        }
        return 0;
    }
}
